n=50;
m=1000;
k=1;
D=[6,2,10,3,7,2,7,6,10,8,2,5,1,10,4,1,1,9,3,1,1,7,10,10,5,5,2,1,4,5,5,10,3,2,2,4,9,6,7,6,7,6,10,6,1,5,6,4,4];
T=[292,50,74,2,60,95,7,281,21,36,10,13,114,15,63,25,33,3,271,30,5,64,1,151,65,117,78,68,1,71,31,41,103,67,35,5,57,38,84,4,120,6,41,1,120,59,45,146,37,14,243,28,201,52,1,19,3,106,172,46,10,32,29,54,184,10,33,26,15,1,63,39,43,61,11,29,100,12,124,55,31,2,229,131,68,100,38,152,3,57,13,77,34,4,58,12,49,27,123,55,49,183,60,212,160,78,93,31,86,214,50,22,1,37,136,26,2,133,180,10,22,12,131,346,81,31,8,9,37,126,10,11,8,106,67,38,34,142,11,31,211,30,163,30,26,29,116,16,20,3,4,95,9,1,27,11,264,1,16,13,178,23,45,74,1,8,137,24,1,7,168,117,131,40,62,8,180,146,11,81,77,59,21,180,41,46,18,135,28,325,1,26,9,1,2,5,10,30,57,10,7,20,176,13,1,74,1,1,145,105,3,132,23,15,87,143,41,8,30,99,66,46,28,24,86,1,38,23,55,20,8,31,106,1,228,12,17,167,50,47,90,148,250,99,96,7,1,96,106,6,88,27,1,96,71,11,135,144,1,139,8,35,72,20,194,134,189,9,176,75,5,63,7,21,1,202,63,2,319,150,5,146,23,43,166,161,43,24,193,2,19,35,5,376,64,45,31,192,129,6,79,16,5,56,155,141,45,32,3,4,31,31,1,197,13,50,30,101,8,21,7,61,2,1,47,39,97,97,1,16,41,4,5,115,22,69,46,87,70,112,6,1,158,4,31,64,37,168,1,99,38,127,146,387,21,71,59,29,4,18,21,50,237,38,314,17,143,129,24,20,166,158,1,7,15,100,37,39,154,4,1,242,12,141,118,1,3,20,28,35,20,59,5,22,8,7,1,45,10,66,28,42,196,69,1,61,20,37,23,57,1,14,1,9,1,213,69,57,28,1,252,1,135,12,4,92,132,129,1,7,41,159,41,56,39,3,53,29,5,2,11,247,341,5,256,7,7,37,35,152,75,159,146,1,26,10,1,80,9,68,21,42,96,113,75,1,175,49,2,10,20,65,1,43,29,103,19,15,128,150,33,133,124,62,111,6,37,18,34,182,21,23,1,7,205,1,143,7,1,13,84,23,53,18,200,15,1,31,61,91,1,25,205,70,42,25,10,3,85,260,16,30,282,5,45,61,23,1,35,23,12,41,93,2,6,1,45,1,13,96,8,8,9,200,25,18,68,21,16,40,37,32,42,42,5,244,52,122,239,13,1,166,80,245,1,15,8,27,133,8,62,16,28,78,42,45,14,1,54,23,5,116,52,1,14,140,22,10,28,19,47,6,100,6,11,1,27,9,172,28,1,117,18,293,20,165,1,24,1,26,21,52,14,21,31,1,193,22,92,126,32,4,20,131,15,31,23,9,88,36,141,10,21,5,71,35,1,39,2,11,129,1,19,178,97,51,11,1,36,87,71,1,10,49,139,37,92,109,13,24,22,1,90,13,34,39,13,6,25,179,135,5,193,8,160,281,114,115,67,29,183,90,121,114,80,60,2,1,30,24,17,11,27,19,12,150,91,75,128,7,143,165,4,1,103,1,14,1,101,14,1,1,59,40,46,10,20,11,8,103,155,91,77,26,102,1,104,28,81,77,57,119,22,1,133,1,108,11,61,29,17,31,1,97,1,71,7,101,27,30,40,3,23,7,19,138,265,26,92,1,350,13,43,115,5,1,1,32,172,2,121,3,108,16,1,21,90,8,39,280,63,55,1,166,6,1,17,1,85,110,110,125,4,33,11,112,11,177,53,48,150,101,49,12,14,42,13,98,1,198,76,59,13,88,136,17,224,20,11,181,7,19,102,118,102,44,8,14,6,272,7,21,8,16,9,22,1,49,88,16,90,35,140,1,160,6,68,146,142,71,1,112,111,5,37,22,5,25,1,1,178,119,10,1,20,19,51,7,1,22,1,1,24,38,62,19,20,11,363,153,77,105,12,96,31,215,4,243,1,205,51,1,10,21,80,5,36,1,137,131,164,143,142,270,2,74,232,172,57,8,38,45,10,22,2,64,1,272,103,115,313,78,157,3,93,2,82,32,15,24,58,160,6,71,3,131,13,73,136,1,25,189,205,23,11,48,188,239,1,1,40,1,50,17,3,14,72,13,35,7,4,39,181,340,3,292,190,6,1,123,131,65,1,378,1,81,25,156,94,8,38,39,151,23,6,54,21,53,1,39,8,26,22,1,24,50,144,91,157,1];
A=[36,7,29,2,14,19,2,34,3,5,3,3,17,37,15,10,9,2,30,12,2,12,1,31,13,30,10,10,1,8,16,25,12,18,8,9,15,22,19,5,23,24,11,2,13,14,10,23,15,4,28,4,41,43,1,4,7,16,20,9,11,13,12,9,34,5,5,10,10,1,11,10,12,7,2,13,19,3,18,8,6,3,39,34,10,11,20,20,3,17,8,10,13,8,23,3,6,9,37,8,11,23,7,34,17,28,22,9,19,28,9,4,1,11,16,5,5,15,32,4,18,6,27,47,10,4,8,2,9,27,7,7,9,29,8,10,8,22,8,4,29,12,26,4,8,4,18,3,3,2,29,18,2,1,9,4,41,1,10,4,26,11,6,11,1,12,19,40,1,4,27,30,19,36,21,3,44,33,12,14,10,15,6,19,5,6,4,16,4,35,5,7,3,1,8,8,38,4,15,5,2,3,26,18,1,9,1,2,43,19,2,24,11,3,12,16,5,2,11,15,9,8,12,4,14,1,13,5,17,33,12,20,35,1,42,16,3,24,19,8,15,31,35,12,22,6,1,22,20,2,12,10,19,18,17,4,20,24,1,15,2,6,10,14,28,19,22,10,31,9,5,13,3,20,1,34,9,3,42,20,3,24,43,11,27,31,10,38,25,2,3,9,5,45,20,6,9,35,19,3,9,10,5,20,22,21,11,10,2,6,10,8,22,23,3,7,4,31,6,25,3,18,2,1,6,7,12,30,1,7,14,4,5,13,17,10,9,10,28,14,6,2,21,5,25,12,5,27,1,15,14,22,31,40,4,22,15,5,2,4,4,7,29,5,40,9,32,14,13,3,22,19,1,2,4,16,11,18,25,4,1,31,21,15,14,1,4,17,8,5,3,12,2,26,5,15,1,18,4,29,7,13,32,9,1,9,3,11,4,12,1,7,1,2,6,27,8,46,17,1,28,2,30,4,8,12,18,20,1,2,6,20,9,11,14,2,9,8,2,2,2,28,36,3,30,20,14,16,18,17,31,20,18,2,5,4,1,24,2,10,3,9,11,18,9,1,25,27,3,14,3,13,1,11,5,14,21,13,20,20,5,24,14,12,18,2,7,4,26,45,3,8,1,2,25,1,28,6,1,16,14,7,29,3,26,8,1,28,13,14,1,4,22,15,14,15,2,37,11,27,3,4,36,2,7,19,5,1,12,5,3,6,14,3,2,9,11,8,17,11,4,2,2,34,7,6,30,5,6,6,5,16,27,13,10,28,18,43,28,4,1,32,18,37,1,5,2,8,19,3,8,12,4,18,6,14,3,4,16,12,3,20,10,2,5,15,4,2,5,4,10,2,30,3,2,1,8,9,20,9,1,13,21,44,3,22,1,4,1,33,6,33,28,5,17,1,25,13,42,20,13,2,3,16,7,4,22,8,13,6,18,16,3,9,9,5,1,9,4,2,25,1,14,30,14,18,2,1,5,11,13,1,27,12,23,8,11,12,5,6,4,1,13,11,15,5,12,2,17,24,27,3,30,4,30,45,15,22,9,7,25,12,20,18,9,33,5,36,17,6,5,2,8,16,6,37,10,9,21,2,21,18,6,1,33,1,4,1,15,32,2,1,10,13,32,2,5,2,9,19,21,29,21,10,19,1,15,4,25,11,11,14,4,11,27,2,32,5,21,4,3,4,1,24,1,22,2,16,5,9,8,6,14,6,10,21,30,7,32,1,38,18,15,18,5,1,1,6,19,2,21,3,14,8,1,3,15,19,8,32,9,8,2,36,6,5,3,1,13,22,19,23,4,8,2,14,5,35,8,10,27,15,6,6,4,8,9,27,1,40,21,7,3,10,17,3,41,7,11,19,2,3,16,20,14,7,4,5,4,33,29,3,9,4,2,8,4,15,11,4,10,8,16,1,31,2,8,16,26,9,1,21,41,2,5,5,2,5,1,1,23,18,11,1,3,3,7,4,1,5,1,6,4,14,9,3,8,3,41,26,27,18,6,15,4,24,2,37,1,31,10,1,3,3,9,2,8,1,15,15,19,16,39,35,5,12,34,29,8,5,13,6,16,4,15,11,1,33,15,15,35,29,31,3,14,15,13,21,31,5,14,21,2,8,13,30,4,25,22,1,4,29,32,5,3,9,25,28,1,2,9,2,34,6,2,18,12,12,5,2,11,6,37,38,12,36,22,2,2,17,33,11,1,39,1,28,5,27,17,4,19,9,16,17,2,11,3,8,1,5,10,4,12,1,7,13,19,10,29,1];
B=[46,9,46,29,38,20,28,45,40,21,43,17,41,38,37,14,18,14,32,23,38,23,3,36,50,33,28,42,6,45,47,35,16,42,44,17,25,30,22,19,31,33,16,3,40,26,19,44,26,29,32,6,46,44,2,13,10,24,43,10,14,36,16,39,48,7,30,39,21,2,25,39,45,48,7,25,29,17,46,9,7,40,46,50,23,33,28,41,16,35,34,14,16,49,31,11,48,41,38,10,25,44,11,45,31,42,29,42,21,49,29,29,2,18,26,33,49,33,46,25,33,41,46,49,19,8,23,6,26,36,29,9,20,33,29,12,14,42,12,24,33,48,28,12,13,7,21,4,37,4,42,50,20,2,15,10,46,33,32,48,42,46,7,25,3,30,33,44,8,18,42,36,40,50,43,16,47,49,30,16,12,20,11,42,26,48,17,31,13,40,24,9,6,2,12,17,42,48,37,30,19,33,40,26,16,25,49,9,44,20,8,39,20,4,48,43,10,21,16,47,10,16,27,28,41,6,26,38,36,44,40,41,47,28,50,23,8,41,40,17,26,46,41,27,29,11,3,38,38,3,15,27,44,46,28,26,46,41,7,40,23,8,41,31,37,20,49,13,46,34,30,19,13,36,5,37,12,4,50,26,27,31,48,18,39,49,13,48,40,20,25,13,43,46,47,23,17,43,48,16,10,45,23,48,23,38,15,13,13,35,36,15,36,33,35,42,19,33,21,46,35,40,5,2,11,27,47,31,20,21,23,27,19,31,33,26,21,35,44,20,13,4,44,16,43,46,43,46,16,45,34,27,34,41,32,26,48,21,27,16,41,11,44,34,50,14,47,24,26,4,30,43,10,3,19,28,14,27,46,17,2,33,30,47,30,2,14,31,33,7,7,22,17,31,6,34,2,40,48,44,8,29,44,11,20,17,33,39,5,15,34,9,37,7,14,33,16,48,20,27,31,8,38,15,33,14,46,37,34,40,46,29,28,13,46,5,16,12,3,3,4,41,49,10,40,21,44,21,36,27,44,42,21,4,28,6,6,47,3,20,7,19,17,34,12,2,50,31,6,17,15,34,3,41,26,50,26,14,22,40,12,29,35,23,24,9,23,47,41,46,30,12,9,10,33,2,48,49,4,22,21,31,32,7,31,46,24,38,14,20,8,49,36,38,41,50,33,39,24,28,7,9,48,13,28,42,10,11,23,6,8,30,34,16,4,38,45,15,35,13,7,20,12,41,36,33,47,6,9,18,43,22,46,41,12,29,24,50,48,10,2,39,42,38,2,40,6,38,43,30,34,14,42,20,22,33,45,7,39,14,43,22,41,37,32,21,5,50,29,36,27,24,35,47,3,24,32,13,26,16,7,16,32,47,6,46,47,15,9,39,8,48,34,50,22,2,45,29,49,37,18,4,4,35,12,7,34,9,44,23,20,25,23,10,11,20,30,10,26,32,44,4,28,35,38,28,4,19,8,13,15,5,34,14,43,45,14,41,39,26,24,4,28,27,34,13,26,4,40,39,43,17,35,7,36,46,28,28,23,9,28,20,22,19,16,34,10,48,41,7,22,7,23,26,17,41,28,10,22,4,31,29,41,4,42,3,18,2,28,41,5,4,12,17,40,4,6,4,28,48,25,40,46,16,22,8,28,8,48,30,22,26,10,20,37,35,44,9,32,23,9,6,2,27,10,49,10,25,14,16,10,25,25,30,11,29,35,47,42,2,48,41,22,33,21,2,15,17,20,14,45,43,16,12,10,45,30,23,44,49,45,9,5,43,23,12,5,2,32,46,39,27,9,11,43,50,6,49,38,32,46,17,13,18,7,9,12,49,3,43,32,10,12,18,23,41,47,47,17,25,3,10,36,46,38,11,6,10,28,38,40,15,26,13,5,49,42,17,41,12,18,25,30,2,35,29,21,20,32,42,5,30,46,26,6,15,9,9,2,4,27,31,46,2,42,8,31,38,2,9,8,12,10,38,15,4,50,28,46,33,46,29,26,25,47,42,43,41,9,40,20,3,4,10,36,15,10,2,17,16,33,47,41,48,50,45,48,46,9,23,14,31,41,14,50,44,2,43,33,19,36,37,43,4,49,23,21,37,36,33,39,34,5,46,17,31,8,41,26,2,16,43,34,28,42,10,46,49,37,11,46,8,35,11,21,33,14,21,23,10,18,9,39,50,31,48,31,37,5,47,36,18,25,40,5,31,8,46,21,14,45,10,27,42,6,17,16,50,33,10,15,5,23,2,18,38,31,14,39,8];